Some general remark: The algorithms used relay heavily on optimization. Therefore it is not guranteed that the algorithms will find always a errorfree solution (even when you see the errorfree solution).
Part of the package is a data set about portals in the Leisepark in Berlin, Germany (Ingress intel map).
library("findWeb")
data(leisepark)
head(leisepark)
## name shortname length
## 1 Tombstone Showing A Portal Being Captured Tombstone Showing … 19
## 2 Grabstätte Familie Schultze und Kramer Grab. Fam. Schultze … 21
## 3 Grabstein Hans-Joachim Wilhelm Grab. H-J Wilhelm 17
## 4 Ruhestätte Familie Dellscha Ruhe. Fam. Dellscha 19
## 5 Hängematte Im Leisepark Hängematte Im … 15
## 6 Stolperstein Mendelsohn Stolper. Mendelsohn 19
## lat lon
## 1 52.52955 13.42254
## 2 52.53028 13.42343
## 3 52.52886 13.42308
## 4 52.52963 13.42115
## 5 52.53003 13.42122
## 6 52.53041 13.42391
Convert the latitudes and longitudes to xy-coordinates
xy <- ll2xy(leisepark$lon, leisepark$lat)
head(xy)
## x y
## [1,] 392992.8 5821108
## [2,] 393054.6 5821188
## [3,] 393027.6 5821031
## [4,] 392898.3 5821119
## [5,] 392903.8 5821163
## [6,] 393087.6 5821201
Next, we will create as target linking structure a fishbone (or herringbone) linking structure.
The fishbone(8) structure consists of nine portals, twentyone links and 19 fields. It was one of the popular linking structures since the EXO5 Controller event in October 2017 since it is simple. And in any case no Softbank Ultra Link is necessary to build it.
Then we have to create a starting link structure.
g0 <- web(g, xy)
plot(g0)
There are two requirements for a perfect link structure:
The second condition means that for the fishbone(n) the largest field should contain at least n-2 portals. The error value used is the number of link intersections plus number of portals for each field missing to the target link structure.
The next step is an optimization of the start link structure. The optimizeWeb generates two (at start and end) or even more plots.
Note: the random seed needs to be fixed since the portal positions are generated randomly and the optimization algorithm uses a random search.
set.seed(1)
g1 <- optimizeWeb(g0)
In this case the optmization algorithm has found a solution with no errors. It is not guranteed that the program will find a link structure with no errors!
Since the a random search algorithm is used you may repeat the search several times and may become a different solution.
set.seed(0)
g11 <- optimizeWeb(g0)
However, the solution the program found is not optimal: the outer portals are far away from each other.
g2 <- swapi(g1) # swap 42-16
plot(g2)
The are two parameters you can modify
set.seed(0)
g12 <- optimizeWeb(g0, maxit=1000000) # default: 100000
g02 <- web(g, xy, rot=32) # default: 16
plot(g02)
In general the optimization algorithm will honor it if you have more portals available than your target structure requires.
As the optimization algorithm the link plan created by the software should only be starting point for a real linking plan.
Once you are created a target link structure you need to know which portals to visit and how to link such that you get the maximum number of fields.
We follow the half-plan approach as shown in the video of Michael Hartley: A Fully General Ingress Maxfields Algorithm. The screen shot shows an agent who has a general walking direction east south east (= -22.5 degree or approx -0.0175 radian).
We use the first linking structure which as been created for the Leisepark
g2 <- linkPlan1(g1)
## [1] -1.996555
# agent comes from -1.877423 radian or -107 degree or south south west
plot(g2)
The agent starts at portal blue 9, walks to portal blue 8, … until finally he ends up at portal blue 2, following the pink line.
You may visually check the path and the link plan by (press enter after each agent move)
getPlan(g2, quiet=TRUE)
The parameter wait determines how the plan is visualiuzed. A negative value (default) means continue after keypress, a positive value continues after wait seconds and a zero does not plot the plan at all.
Now lets head the agent mainly in direction east, coming from the west (= -180 degree = -3.1415 radian)
g2 <- linkPlan1(g1, dir=-pi)
## [1] -3.141593
# 2.215663 rad approx. 127 degree,
# agent walks comes approxmately from direction north west
plot(g2)
And which keys (and softbank ultralinks) are required to build the structure:
g3 <- linkPlan1(g1)
## [1] -1.996555
plot(g3)
getPlan(g3, wait=0)
##
## Walk 'n link agent 1 (560 m as the crow flies)
## Portal Link to
## [1,] "11" NA
## [2,] "33" "11"
## [3,] "24" "33"
## [4,] "42" "24"
## [5,] "32" "42"
## [6,] "7" "32"
## [7,] "20" "7"
## [8,] "37" "11"
## [9,] "37" "33"
## [10,] "37" "24"
## [11,] "37" "42"
## [12,] "37" "32"
## [13,] "37" "7"
## [14,] "37" "20"
## [15,] "6" "11"
## [16,] "6" "37"
## [17,] "6" "33"
## [18,] "6" "24"
## [19,] "6" "42"
## [20,] "6" "32"
## [21,] "6" "7"
## [22,] "6" "20"
##
## Required items
## 6 37 20 7 32 42 24 33 11 SBUL
## 1 0 1 2 3 3 3 3 3 3 0
## Total 0 1 2 3 3 3 3 3 3 0
getPlan(g3, names=leisepark$shortname, wait=0)
##
## Walk 'n link agent 1 (560 m as the crow flies)
## Portal Link to
## [1,] "Grab. Fam. Fritz Jahn" NA
## [2,] "Grab. Fam. Ende" "Grab. Fam. Fritz Jahn"
## [3,] "Grab. Fam. Heller" "Grab. Fam. Ende"
## [4,] "Relief" "Grab. Fam. Heller"
## [5,] "Grab. Fam. Ecke" "Relief"
## [6,] "Grab. Ottokar Dohms" "Grab. Fam. Ecke"
## [7,] "Grab. Fam. Kloecke" "Grab. Ottokar Dohms"
## [8,] "Holzmikado" "Grab. Fam. Fritz Jahn"
## [9,] "Holzmikado" "Grab. Fam. Ende"
## [10,] "Holzmikado" "Grab. Fam. Heller"
## [11,] "Holzmikado" "Relief"
## [12,] "Holzmikado" "Grab. Fam. Ecke"
## [13,] "Holzmikado" "Grab. Ottokar Dohms"
## [14,] "Holzmikado" "Grab. Fam. Kloecke"
## [15,] "Stolper. Mendelsohn" "Grab. Fam. Fritz Jahn"
## [16,] "Stolper. Mendelsohn" "Holzmikado"
## [17,] "Stolper. Mendelsohn" "Grab. Fam. Ende"
## [18,] "Stolper. Mendelsohn" "Grab. Fam. Heller"
## [19,] "Stolper. Mendelsohn" "Relief"
## [20,] "Stolper. Mendelsohn" "Grab. Fam. Ecke"
## [21,] "Stolper. Mendelsohn" "Grab. Ottokar Dohms"
## [22,] "Stolper. Mendelsohn" "Grab. Fam. Kloecke"
##
## Required items
## Stolper. Mendelsohn Holzmikado Grab. Fam. Kloecke
## 1 0 1 2
## Total 0 1 2
## Grab. Ottokar Dohms Grab. Fam. Ecke Relief Grab. Fam. Heller
## 1 3 3 3 3
## Total 3 3 3 3
## Grab. Fam. Ende Grab. Fam. Fritz Jahn SBUL
## 1 3 3 0
## Total 3 3 0
For creating a link plan for several agents we follow a different approach. We do it the japanese way starting from the center and building the fields to the outer.
Â
From a starting portal (red) we decompose the area in n sectors (here n=3 sectors). Each of the n agents goes to the portals in his sector and links back to all the portals all the agents have visited already.
NOTE: Is is not clear if this approach leads always to the maximum field number!
As a first step we will create a cobweb with three portals at each leg
g <- cobweb(3)
plot(g)
Then find a solution at the Leisepark
g0 <- web(g, xy)
set.seed(1)
g1 <- optimizeWeb(g0)
plot(g1)
Finally we create a link plan for three agents
g2 <- linkPlanN(g1, agents=3)
plot(g2)
and look for the linking and the keys
getPlan(g2, wait=1)
## Agent: 1, Portal: 38, SBULs: -0, Link to:
## Agent: 2, Portal: 38, SBULs: -0, Link to:
## Agent: 3, Portal: 38, SBULs: -0, Link to:
## Agent: 1, Portal: 42, SBULs: 0, Link to: 38
## Agent: 3, Portal: 7, SBULs: 0, Link to: 38,42
## Agent: 2, Portal: 34, SBULs: 0, Link to: 42,7,38
## Agent: 1, Portal: 33, SBULs: 0, Link to: 34,42
## Agent: 3, Portal: 20, SBULs: 0, Link to: 34,33,42,7
## Agent: 3, Portal: 39, SBULs: 0, Link to: 33,20
## Agent: 1, Portal: 15, SBULs: 0, Link to: 39,33
## Agent: 2, Portal: 17, SBULs: 0, Link to: 15,39,33,20,34
##
## Walk 'n link agent 1 (124 m as the crow flies)
## Portal Link to
## [1,] "38" NA
## [2,] "42" "38"
## [3,] "33" "34"
## [4,] "33" "42"
## [5,] "15" "39"
## [6,] "15" "33"
##
## Walk 'n link agent 2 (135 m as the crow flies)
## Portal Link to
## [1,] "38" NA
## [2,] "34" "42"
## [3,] "34" "7"
## [4,] "34" "38"
## [5,] "17" "15"
## [6,] "17" "39"
## [7,] "17" "33"
## [8,] "17" "20"
## [9,] "17" "34"
##
## Walk 'n link agent 3 (114 m as the crow flies)
## Portal Link to
## [1,] "38" NA
## [2,] "7" "38"
## [3,] "7" "42"
## [4,] "20" "34"
## [5,] "20" "33"
## [6,] "20" "42"
## [7,] "20" "7"
## [8,] "39" "33"
## [9,] "39" "20"
##
## Required items
## 17 15 39 34 33 20 38 42 7 SBUL
## 1 0 0 1 1 1 0 1 1 0 0
## 2 0 1 1 1 1 1 1 1 1 0
## 3 0 0 0 1 2 1 1 2 1 0
## Total 0 1 2 3 4 2 3 4 2 0
Of course, a single agent could have done it alone ;)
g4 <- linkPlan1(g1, direction=-pi)
## [1] -3.141593
getPlan(g4, wait=1)
## Agent: 1, Portal: 15, SBULs: -0, Link to:
## Agent: 1, Portal: 33, SBULs: 0, Link to: 15
## Agent: 1, Portal: 42, SBULs: 0, Link to: 33
## Agent: 1, Portal: 38, SBULs: 0, Link to: 42
## Agent: 1, Portal: 7, SBULs: 0, Link to: 42,38
## Agent: 1, Portal: 39, SBULs: 0, Link to: 15,33
## Agent: 1, Portal: 20, SBULs: 0, Link to: 33,42,39,7
## Agent: 1, Portal: 34, SBULs: 0, Link to: 33,20,42,7,38
## Agent: 1, Portal: 17, SBULs: 0, Link to: 15,39,33,20,34
##
## Walk 'n link agent 1 (469 m as the crow flies)
## Portal Link to
## [1,] "15" NA
## [2,] "33" "15"
## [3,] "42" "33"
## [4,] "38" "42"
## [5,] "7" "42"
## [6,] "7" "38"
## [7,] "39" "15"
## [8,] "39" "33"
## [9,] "20" "33"
## [10,] "20" "42"
## [11,] "20" "39"
## [12,] "20" "7"
## [13,] "34" "33"
## [14,] "34" "20"
## [15,] "34" "42"
## [16,] "34" "7"
## [17,] "34" "38"
## [18,] "17" "15"
## [19,] "17" "39"
## [20,] "17" "33"
## [21,] "17" "20"
## [22,] "17" "34"
##
## Required items
## 17 15 39 34 33 20 38 42 7 SBUL
## 1 0 3 2 1 5 2 2 4 2 0
## Total 0 3 2 1 5 2 2 4 2 0
The plot command offers additional parameters which are set on TRUE by default.
plot(g4, blue=FALSE) # do not plot the blue numbers
plot(g4, black=FALSE) # do not plot the black numbers
plot(g4, links=FALSE) # do not plot the links
plot(g4, pathes=FALSE) # do not plot the agent pathes
To simplify the typing you may use the forward pipe operator %>% of the library magrittr. Instead of writing
g0 <- fishbone(8)
g1 <- web(g0, xy)
g2 <- optimizeWeb(g1)
g3 <- linkPlan1(g2)
plot(g3, blue=FALSE)
you may use
library("magrittr") # for %>% operator
fishbone(8) %>% web(xy) %>% optimizeWeb() %>% linkPlan1() %>% plot(blue=FALSE)
## [1] -1.842887
Or alternatively
g <- fishbone(8) %>% web(xy) %>% optimizeWeb() %>% linkPlan1()
plot(g, blue=FALSE)
Finally, a thanks to Stefan Dirsch for testing the R package, Michael Hartley for his videos and the authors of R package FNN: Fast Nearest Neighbor Search Algorithms and Applications ;)